UVa/378 - Intersecting lines/378.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <map>
  19 #include <set>
  20
  21 #define D(x) cout << #x " is " << x << endl
  22
  23 /*
  24   Finds the intersection between two lines (Not segments! Infinite lines)
  25   Line 1 passes through points (x0, y0) and (x1, y1).
  26   Line 2 passes through points (x2, y2) and (x3, y3).
  27
  28   Handles the case when the 2 lines are the same (infinite intersections),
  29   parallel (no intersection) or only one intersection.
  30 */
  31 void line_line_intersection(double x0, double y0,   double x1, double y1,
  32                             double x2, double y2,   double x3, double y3){
  33 #ifndef EPS
  34 #define EPS 1e-9
  35 #endif
  36
  37   double t0 = (y3-y2)*(x0-x2)-(x3-x2)*(y0-y2);
  38   double t1 = (x1-x0)*(y2-y0)-(y1-y0)*(x2-x0);
  39   double det = (y1-y0)*(x3-x2)-(y3-y2)*(x1-x0);
  40   if (fabs(det) < EPS){
  41     //parallel
  42     if (fabs(t0) < EPS || fabs(t1) < EPS){
  43       //same line
  44       printf("LINE\n");
  45     }else{
  46       //just parallel
  47       printf("NONE\n");
  48     }
  49   }else{
  50     t0 /= det;
  51     t1 /= det;
  52     double x = x0 + t0*(x1-x0);
  53     double y = y0 + t0*(y1-y0);
  54     //intersection is point (x, y)
  55     printf("POINT %.2lf %.2lf\n", x, y);
  56   }
  57 }
  58
  59 int main(){
  60   int n;
  61   scanf("%d", &n);
  62   printf("INTERSECTING LINES OUTPUT\n");
  63   while (n--){
  64     double x0,y0, x1,y1,    x2,y2, x3,y3;
  65     scanf("%lf %lf %lf %lf %lf %lf %lf %lf",
  66           &x0, &y0, &x1, &y1, &x2, &y2, &x3, &y3);
  67     line_line_intersection(x0,y0, x1,y1,    x2,y2,  x3,y3);
  68   }
  69   printf("END OF OUTPUT\n");
  70   return 0;
  71 }